//
// Created by Administrator on 2021/8/30.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>
#include <random>

using namespace std;

class Solution {
private:
    mt19937 gen; // 随机数生成器
    uniform_int_distribution<int> dis; // 随机分布
    vector<int> pre; // 前缀和数组
public:
    Solution(vector<int> &w) : gen(random_device{}()), dis(1, accumulate(w.begin(), w.end(), 0)) {
        partial_sum(w.begin(), w.end(), back_inserter(pre)); // 求前缀和
    }

    int pickIndex() {
        int x = dis(gen); // 随机生成一个 1 到 w总和的数字
        return lower_bound(pre.begin(), pre.end(), x) - pre.begin(); // 二分查找 >=
    }
};

int main() {
    vector<int> weights{1, 3};
    Solution solution(weights);
    cout << solution.pickIndex() << endl;
    cout << solution.pickIndex() << endl;
    cout << solution.pickIndex() << endl;
    cout << solution.pickIndex() << endl;
    cout << solution.pickIndex() << endl;
    return 0;
}
